package my.algorithms.mcorrea.datastructures;

/**
 *
 * @author mcorrea
 */
public class BinaryTree {

	private Node root;
	
	public BinaryTree(){}
	
	public void insert(Integer value){
		if(root !=null ){
			insertNode(root, value);
		}else{
			root = new Node(null, null, value);		
		}
	}
	
	private void insertNode(Node parent, Integer value){
		if(value < parent.getValue()){//go left
			if(parent.getLeft()!=null){
				insertNode(parent.getLeft(), value);
			}else{
				Node temp = new Node(null, null, value);
				parent.setLeft(temp);
			}
		}else if(value >= parent.getValue()){//go right, for understanding do valdation
			if(parent.getRight()!=null){
				insertNode(parent.getRight(), value);
			}else{
				Node temp = new Node(null, null, value);
				parent.setRight(temp);
			}
		
		}
	}
	
	public boolean contains(Integer value){
		
		if(root!=null){
			return contains(root, value);
		}
		return false;
		
	}
	
	private boolean contains(Node node, Integer value){
		if(node.getValue() == value){
			return true;
		}else{
			if(value < node.getValue() ){
				if (node.getLeft()!=null){
					return contains(node.getLeft(), value);
				}else{
					return false; 
				}
			}else{
				if(value >= node.getValue() ){
					if (node.getRight()!=null){
						return contains(node.getRight(), value);
					}else{
						return false; 
					}
				}
			}
		}
		return false;
	}
	
	
	public void inorderPrint(){
		if(root!=null){
			inorderPrint(root);
		}else{
			System.out.println("Empty tree...");
		}
	}
	
	private void inorderPrint(Node node){
		System.out.print(node.getValue()+" ");if(node.getLeft()!=null){
			inorderPrint(node.getLeft());
		}
		System.out.print(node.getValue()+" ");
		if(node.getRight()!=null){
			inorderPrint(node.getRight());
		}
	}
	
	
	protected class Node{
		
		private Node right;
		private Integer value; 
		private Node left;
		
		public Node(Node right, Node left, Integer value){
			this.right = right;
			this.left = left;
			this.value = value;
		}

		public Node getLeft() {
			return left;
		}

		public void setLeft(Node left) {
			this.left = left;
		}

		public Node getRight() {
			return right;
		}

		public void setRight(Node right) {
			this.right = right;
		}

		public Integer getValue() {
			return value;
		}

		public void setValue(Integer value) {
			this.value = value;
		}
	}
	
	
	public static void main(String args[]){
		BinaryTree tree = new BinaryTree();
		tree.insert(10);
		tree.insert(5);
		tree.insert(20);
		tree.insert(4);
		tree.insert(7);
		tree.insert(25);
		tree.insert(18);
		tree.inorderPrint();
		System.out.println();
		System.out.println(tree.contains(4));
		System.out.println(tree.contains(50));
		
	
	}
	
	
}
